package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 1/20/21 2:18 PM
 *
 *  https://leetcode-cn.com/problems/maximum-product-subarray/
 */
public class _152_乘积最大子数组 {

    private int max = Integer.MIN_VALUE;

    public int maxProduct(int[] nums) {

        if (nums == null || nums.length == 0) {
            return 0;
        }

        if (nums.length == 1) {

            return nums[0];
        }

        int resMax = nums[0];

        int preMax = resMax,preMin =resMax;

        for (int i = 1; i < nums.length; i++) {

            int m1 = preMax * nums[i];
            int m2 = preMin * nums[i];
            int m3 = nums[i];

            preMax = Math.max(Math.max(m1,m2),m3);
            preMin = Math.min(Math.min(m1,m2),m3);
            resMax = Math.max(resMax,preMax);
        }

        return resMax;
    }

    private void findMax(int[] nums, int index,int all) {

        if (index == nums.length) {
            // 第一个直接返回
            return;
        }

        // 不从index开始
        int have = all * nums[index];
        max = Math.max(Math.max(max,have),nums[index]);
        findMax(nums, index + 1,have);
        // 从index
        findMax(nums,index + 1, nums[index]);
    }

  public static void main(String[] args) {
    //

      _152_乘积最大子数组 maxProduct = new _152_乘积最大子数组();
      /**
       * 6 -2 -12
       * 3 -6
       *  -2
       */
      int[] nums = {0,-1,4,-4,5,-2,-1,-1,-2,-3,0,-3,0,1,-1,-4,4,6,2,3,0,-5,2,1,-4,-2,-1,3,-4,-6,0,2,2,-1,-5,1,1,5,-6,2,1,-3,-6,-6,-3,4,0,-2,0,2};
      int result = maxProduct.maxProduct(nums);
      System.out.println(result);
  }
}
